An image is made up of visual elements, wherein a visual element is defined as a region in a sampled image. A commonly used visual element in image processing is a picture element or pixel. However, image processing on a pixel level is often slow for mega-pixel or bigger images. By grouping connected pixels that share common properties such as intensity, colour or texture into a superpixel, the image can advantageously be analysed at a higher granularity level and consequently at a faster processing speed (or, alternatively, with requiring less processing resources). Partitioning of an image into such groups of pixels is known as superpixel segmentation.
Over-segmentation of an image into regular sized and shaped superpixels that respect scene boundaries is useful for subsequent image processing tasks. Regular superpixel segmentation produces compact visual elements of similar size and shape for similar treatment of an image's local neighbourhood. Boundary-respecting superpixels are more likely to cover pixels from the same object in a scene, which further improves the localisation of subsequent image processing measures.
One approach is watershed segmentation, which over-segments an image by flooding a landscape defined by the image's gradient magnitude and building watersheds along ridges that divide different water catchment basins. More efficient methods such as graph-based segmentation can also produce edge-following segmentation, which means that edges in the image are well tracked by the segmentation boundaries. Both watershed and graph-based segmentation, however, produce irregularly sized and shaped segments.
Other techniques produce regular superpixels. One such method uses curve evolution to guide superpixel boundaries from a set of seed points on a rectangular grid towards scene boundaries. A significant disadvantage of the curve evolution method is its slow speed since the method typically requires hundreds of curve evolution iterations, especially if the superpixels are large.
Another such method uses a linear iterative clustering of local pixels in a five-dimensional (5-D) Labxy space defined by the L*-a*-b* colours from the CIE standard and the x-y pixel coordinates. Similar to the curve evolution method, the initial cluster centres of the iterative clustering method also come from a set of points on a regular grid. Both the curve evolution method and the iterative clustering method disadvantageously require multiple scans (typically more than 10) over a derived image. These methods are therefore not suitable for hardware environments in which limited on-chip memory cannot buffer the whole image and real-time performance is critical.
None of the above-mentioned segmentation methods can produce an exact desirable number of superpixels. An exact number of superpixels is useful for resource planning, for example, sending each superpixel to different parallel computing units. An exact number of superpixels is also useful for matching two or more images of similar content so that each superpixel in one image has an unique corresponding superpixel in another image.
In summary, there is a need for a segmentation method that achieves one or more desirable characteristics of good superpixel segmentation, including: edge-following, regularity, exact number of segments and practical computational requirements. In particular, there is a need for an improved method and system for rapidly segmenting an image into a desirable number of regular, edge-following superpixels.